package com.sicheng.蓝桥.练习题.线段树.动态开点;


/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/25 23:11
 */
@SuppressWarnings("all")
public class 统计区间整数数目 {
    static class Tree {
        int ls;
        int rs;
        int w;
        int lazy;
    }

    int N = (int) (1e9 + 1);
    int cnt = 1;
    int M = (int) 1e6;
    Tree[] tree = new Tree[M];

    void lazyCreate(int st) {
        if (tree[st] == null) {
            tree[st] = new Tree();
        }
        if (tree[st].ls == 0) {
            tree[st].ls = ++cnt;
            tree[tree[st].ls] = new Tree();
        }
        if (tree[st].rs == 0) {
            tree[st].rs = ++cnt;
            tree[tree[st].rs] = new Tree();
        }
    }

    public void add(int l, int r) {
        update(l, r, 1, 1, N);
    }

    void update(int l, int r, int st, int ll, int rr) {
        lazyCreate(st);
        if (tree[st].lazy == 1) {
            return;
        }
        if (l == ll && r == rr) {
            tree[st].w = r - l + 1;
            tree[st].lazy = 1;
            return;
        }
        int mid = ll + rr >> 1;
        if (r <= mid) {
            update(l, r, tree[st].ls, ll, mid);
        } else if (l > mid) {
            update(l, r, tree[st].rs, mid + 1, rr);
        } else {
            update(l, mid, tree[st].ls, ll, mid);
            update(mid + 1, r, tree[st].rs, mid + 1, rr);
        }
        pushUp(st);
    }

    public int count() {
        return tree[1] == null ? 0 : tree[1].w;
    }

    void pushUp(int st) {
        tree[st].w = tree[tree[st].ls].w + tree[tree[st].rs].w;
    }

    //    https://leetcode.cn/problems/count-integers-in-intervals/
    public static void main(String[] args) {
        统计区间整数数目 solution = new 统计区间整数数目();

        solution.add(2, 3);
        solution.add(7, 10);
        solution.add(5, 8);
    }

}
